class ArrayQueue:
    """基于数组的队列"""
    DEFAULT_LENGTH = 10

    def __init__(self):
        self.queue = [None] * self.DEFAULT_LENGTH
        self.size = 0
        self.front = 0

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def first(self):
        if self.is_empty():
            raise Exception('队列为空')
        return self.queue[self.front]

    def dequeue(self):
        """出队"""
        if self.is_empty():
            raise Exception('队列为空')
        data = self.queue[self.front]
        self.queue[self.front] = None
        self.size -= 1
        self.front = (self.front + 1) % 10
        if 0 < self.size < (len(self.queue) // 4):
            self.resize(len(self.queue) // 2)
        return data

    def enqueue(self,data):
        """入队"""
        length = len(self.queue)
        if self.size == length:
            self.resize(2 * length)
        end = (self.front + self.size) % 10
        self.queue[end] = data
        self.size += 1

    def resize(self,length):
        old_queue = self.queue
        old_len = len(self.queue)
        self.queue = [None] * length
        index = self.front
        for i in range(self.size):
            self.queue[i] = old_queue[index]
            index = (index + 1) % old_len
        self.front = 0
